package main.Q1_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q51_60 {
    public static void main(String[] args) {
        System.out.println("Question51：N皇后");
        System.out.println("Question52：N皇后Ⅱ");
        System.out.println("Question53：最大子数组和");
        System.out.println("Question54：螺旋矩阵");
        System.out.println("Question55：跳跃游戏");
        System.out.println("Question56：合并区间");
        System.out.println("Question57：插入区间");
        System.out.println("Question58：最后一个单词的长度");
        System.out.println("Question59：螺旋矩阵Ⅱ");
        System.out.println("Question60：排列序列");
    }
}

class Question51{
    List<List<Integer>> indexList;
    int n;
    public List<String> process3(List<Integer> position,int n) {//根据方案得到字符串
        List<String> result=new ArrayList<>();
        for (int index : position) {
            StringBuffer stringBuffer=new StringBuffer();
            for (int i=0;i<n;i++) stringBuffer.append(".");
            stringBuffer.setCharAt(index,'Q');
            result.add(stringBuffer.toString());
        }
        return result;
    }
    public boolean process2(List<Integer> lastList,int index) {//判断该位置是否满足条件
        if (lastList.contains(index)) return false;//存在同一列
        int curLevel=lastList.size();
        for (int i=0;i<lastList.size();i++) {//判断对角线
            int col=lastList.get(i);
            double k=((col-index)*1.0)/((i-curLevel)*1.0);
            if (Math.abs(k)==1) return false;
        }
        return true;
    }
    public void process1(List<Integer> lastList,int level) {//逐层遍历
        List<Integer> curList=new ArrayList<>(lastList);
        if (level>n) {//最后一层完结
            indexList.add(curList);
            return;
        }
        for (int i=0;i<n;i++) {
            if (process2(curList,i)) {
                curList.add(i);
                process1(curList,level+1);//进入下一层
                curList.remove(curList.size()-1);
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        indexList=new ArrayList<>();
        this.n=n;
        List<Integer> curList=new ArrayList<>();
        process1(curList,1);
        List<List<String>> result=new ArrayList<>();
        for (List<Integer> curPosition : indexList) {
            List<String> curString=process3(curPosition,n);
            result.add(curString);
        }
        return result;
    }
}

class Question52{
    List<List<Integer>> indexList;
    int n;
    public List<String> process3(List<Integer> position,int n) {//根据方案得到字符串
        List<String> result=new ArrayList<>();
        for (int index : position) {
            StringBuffer stringBuffer=new StringBuffer();
            for (int i=0;i<n;i++) stringBuffer.append(".");
            stringBuffer.setCharAt(index,'Q');
            result.add(stringBuffer.toString());
        }
        return result;
    }
    public boolean process2(List<Integer> lastList,int index) {//判断该位置是否满足条件
        if (lastList.contains(index)) return false;//存在同一列
        int curLevel=lastList.size();
        for (int i=0;i<lastList.size();i++) {//判断对角线
            int col=lastList.get(i);
            double k=((col-index)*1.0)/((i-curLevel)*1.0);
            if (Math.abs(k)==1) return false;
        }
        return true;
    }
    public void process1(List<Integer> lastList,int level) {//逐层遍历
        List<Integer> curList=new ArrayList<>(lastList);
        if (level>n) {//最后一层完结
            indexList.add(curList);
            return;
        }
        for (int i=0;i<n;i++) {
            if (process2(curList,i)) {
                curList.add(i);
                process1(curList,level+1);//进入下一层
                curList.remove(curList.size()-1);
            }
        }
    }
    public int totalNQueens(int n) {
        indexList=new ArrayList<>();
        this.n=n;
        List<Integer> curList=new ArrayList<>();
        process1(curList,1);
        return indexList.size();
    }
}

class Question53{
    public int maxSubArray(int[] nums) {
        int maxSum=Integer.MIN_VALUE;
        int curSum=0;
        for(int i=0;i<nums.length;i++) {
            curSum+=nums[i];
            maxSum=Math.max(curSum,maxSum);
            if(curSum<0) {// 新增数值无增益
                curSum=0;
            }
        }
        return maxSum;
    }
//    public int maxSubArray(int[] nums) {
//        int max=Integer.MIN_VALUE,length= nums.length;
//        int[] dp=new int[length];
//        for (int i=0;i<length;i++){
//            if (i==0) dp[i]=nums[i];
//            else if (dp[i-1]>0) dp[i]=dp[i-1]+nums[i];
//            else dp[i]=nums[i];
//            max=Math.max(max,dp[i]);
//        }
//        return max;
//    }
}

class Question54{//宏观调度思想
    public void process(int[][] mat, int leftRow, int leftCol, int rightRow, int rightCol, List<Integer> list) {
        if (rightRow < leftRow || rightCol < leftCol) return;
        if (leftRow == rightRow) {// 只有一行时，按「行」遍历
            for (int i = leftCol; i <= rightCol; i++) list.add(mat[leftRow][i]);
            return;
        }
        if (leftCol == rightCol) {// 只有一列时，按「列」遍历
            for (int i = leftRow; i <= rightRow; i++) list.add(mat[i][rightCol]);
            return;
        }
        for (int i = leftCol; i < rightCol; i++) list.add(mat[leftRow][i]);//上行
        for (int i = leftRow; i < rightRow; i++) list.add(mat[i][rightCol]);//右列
        for (int i = rightCol; i > leftCol; i--) list.add(mat[rightRow][i]);//下行
        for (int i = rightRow; i > leftRow; i--) list.add(mat[i][leftCol]);//左列
        process(mat, leftRow + 1, leftCol + 1, rightRow - 1, rightCol - 1, list);//遍历下层
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list=new ArrayList<>();
        int leftRow=0,leftCol=0,rightRow= matrix.length-1,rightCol=matrix[0].length-1;//定义左上角、右下角坐标
        process(matrix,leftRow,leftCol,rightRow,rightCol,list);
        return list;
    }
}

class Question55{
    public boolean canJump(int[] nums) {
        int max=0;
        for (int i=0;i< nums.length;i++){
            if (i<=max) {//当前最远范围内可以到的位置
                if (i + nums[i] > max) max = i + nums[i];//能跳到的最远距离
                if (max >= nums.length - 1) return true;
            }
        }
        return false;
    }
}

class Question56{
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (x, y)-> x[0] - y[0]);
        int l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > r){
                res.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }else{
                r = Math.max(r, intervals[i][1]);
            }
        }
        res.add(new int[]{l, r});
        return res.toArray(new int[0][]);
    }
}

class Question57{
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int length= intervals.length+1,i=0,j=0;
        int[][] result=new int[length][];
        return null;
    }
}

class Question58{
    public int lengthOfLastWord(String s) {
        String[] a;
        int length=-1;
        a=s.split(" ");
        int index=a.length-1;
        while (true){
            if (!a[index].equals("")){
                length=a[index].length();
                break;
            }else index--;
        }
        return length;
    }
}

class Question59{
    public int[][] generateMatrix(int n) {
        int num = 1;
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                matrix[top][column] = num;
                num++;
            }
            for (int row = top + 1; row <= bottom; row++) {
                matrix[row][right] = num;
                num++;
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    matrix[bottom][column] = num;
                    num++;
                }
                for (int row = bottom; row > top; row--) {
                    matrix[row][left] = num;
                    num++;
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
}

class Question60{
    public int process(int n){//获取阶乘
        int multi=1;
        for (int i=1;i<=n;i++) multi*=i;
        return multi;
    }
    public String getPermutation(int n, int k) {
        if (n==1) return "1";
        StringBuffer result=new StringBuffer();
        List<Integer> numList=new ArrayList<>();
        for (int i=1;i<=n;i++) numList.add(i);//所有可用的数
        while (n>2){
            int count=process(n-1);//当前位置开头时，每个数有多少中开头
            int start=0;//以数字哪个数字开头
            if (count!=k) start=k/count;//当相等时，正好以为该开头的最后一个
            if (k%count==0) start--;
            result.append(numList.get(start));
            k=k%count;//下一个位置
            numList.remove(numList.get(start));//将使用过的数字移除
            n--;
            if (k==0) break;
        }
        if (k==1){
            result.append(numList.get(0));//仅剩最后一个数
            result.append(numList.get(1));
        }else {
            for (int i=numList.size()-1;i>=0;i--){
                result.append(numList.get(i));
            }
        }
        return result.toString();
    }
}